﻿#define _CRT_SECURE_NO_WARNINGS 1
//题目：完美牛棚
//农夫约翰上周刚刚建好了新的牛棚，并引进了最新的挤奶技术。
//不幸的是，由于工程问题，牛棚中的每个单间都不太一样。
//第一周，约翰将奶牛们随机分配在了各个单间中。
//但是很快他就发现，每头奶牛都只愿意在一部分自己喜欢的单间中产奶。
//在过去的一周中，农夫约翰一直在收集有关哪些奶牛愿意在哪些单间产奶的数据。
//一个单间只能分配给一头奶牛，当然，一头奶牛也可能只愿意在一个单间中产奶。
//给定奶牛的住宿喜好，请你计算，通过合理分配奶牛的住所，最多能够让多少奶牛可以住在自己愿意产奶的单间中。
//输入格式
//第一行包含两个整数 N和 M，分别表示奶牛的数量以及单间的数量。
//接下来 N行，每行记录一个奶牛愿意产奶的单间信息。首先包含一个整数 Si，表示这头奶牛愿意在 Si个单间中产奶。接下来包含 Si个不同的整数，表示这些单间的编号。
//所有单间的编号为 1∼M。
//输出格式
//输出一个整数，表示可以被分配在自己愿意产奶的单间中的奶牛的最大数量。
//数据范围
//0≤N, M≤200，0≤Si≤M
//输入样例：
//5 5
//2 2 5
//3 2 3 4
//2 1 5
//3 1 2 5
//1 2
//输出样例：
//4
//#include<iostream>
//#include<algorithm>
//#include<cstring>
//using namespace std;
//const int N = 10010;
//int n, m;
//int h[N], ne[N], e[N], idx, match[N];
//bool st[N];
//void add(int a, int b)
//{
//    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
//}
//bool find(int x)
//{
//    for (int i = h[x]; i != -1; i = ne[i])
//    {
//        int j = e[i];
//        if (!st[j])//判断该单间有没有被使用过
//        {
//            st[j] = true;
//            if (match[j] == 0 || find(match[j]))//find指找到该单间连接的奶牛是谁，看看奶牛能不能换别的单间，不能就
//            //让下一个奶牛匹配别的产间了
//            {
//                match[j] = x;
//                return true;
//            }
//        }
//    }
//    return false;
//}
//int main()
//{
//    cin >> n >> m;
//    int res = 0;
//    memset(h, -1, sizeof h);
//    for (int i = 1; i <= n; i++)//n为奶牛的数量
//    {
//        int s;
//        cin >> s;
//        while (s--)
//        {
//            int a;
//            cin >> a;
//            add(i, a);//给每个有意愿产奶的单间连接
//        }
//    }
//    for (int i = 1; i <= n; i++)
//    {
//        memset(st, false, sizeof st);//每次都给单间设置为false;
//        if (find(i)) res++;
//    }
//    cout << res << endl;
//    return 0;
//}

//题目，作物杂交
//作物杂交是作物栽培中重要的一步。
//已知有 N种作物(编号 1至 N)，第 i种作物从播种到成熟的时间为 Ti。
//作物之间两两可以进行杂交，杂交时间取两种中时间较长的一方。
//如作物 A种植时间为 5天，作物 B种植时间为 7天，则 AB杂交花费的时间为 7天。
//作物杂交会产生固定的作物，新产生的作物仍然属于 N种作物中的一种。
//初始时，拥有其中 M种作物的种子(数量无限，可以支持多次杂交)。
//同时可以进行多个杂交过程。
//求问对于给定的目标种子，最少需要多少天能够得到。如存在 4种作物 ABCD，各自的成熟时间为 5天、7天、3天、8天。
//初始拥有 AB两种作物的种子，目标种子为 D，已知杂交情况为 A×B→C，A×C→D。
//则最短的杂交过程为：第 1天到第 7天(作物 B的时间)，A×B→C。
//第 8天到第 12天(作物 A的时间)，A×C→D。
//花费 12天得到作物 D的种子。
//输入格式
//输入的第 1行包含 4个整数 N, M, K, T，N表示作物种类总数(编号 1至 N)，M表示初始拥有的作物种子类型数量，K表示可以杂交的方案数，T表示目标种子的编号。
//第 2行包含 N个整数，其中第 i个整数表示第 i种作物的种植时间 Ti。
//第 3行包含 M个整数，分别表示已拥有的种子类型 Kj，Kj两两不同。
//第 4至 K + 3行，每行包含 3个整数 A, B, C，表示第 A类作物和第 B类作物杂交可以获得第 C类作物的种子。
//输出格式
//输出一个整数，表示得到目标种子的最短杂交时间。
//样例解释
//1≤N≤2000,2≤M≤N,1≤K≤105,1≤T≤N,1≤Ti≤100,1≤Kj≤M,保证目标种子一定可以通过杂交得到。
//不保证作物 A和 B杂交只能生成作物 C（也就是说，A×B→C和 A×B→D可能同时在输入中出现）
//不保证作物 C只能由作物 A和 B杂交生成（也就是说，A×B→D和 A×C→D可能同时在输入中出现）。
//不保证同一杂交公式不在输入中重复出现。
//输入样例：
//6 2 4 6
//5 3 4 6 4 9
//1 2
//1 2 3
//1 3 4
//2 3 5
//4 5 6
//输出样例：
//16
//样例解释
//第 1天至第 5天，将编号 1与编号 2的作物杂交，得到编号 3的作物种子。
//第 6天至第 10天，将编号 1与编号 3的作物杂交，得到编号 4的作物种子。
//第 6天至第 9天，将编号 2与编号 3的作物杂交，得到编号 5的作物种子。
//第 11天至第 16天，将编号 4与编号 5的作物杂交，得到编号 6的作物种子。
//总共花费 16天。

//#include<iostream>
//#include<queue>
//#include<algorithm>
//#include<cstring>
//using namespace std;
//const int N = 2010, M = 200010;//M为200010是因为两节点可以相互杂交，相当于无向
//int h[N], w[N], ne[M], target[M], e[M], idx;//target为两节点杂交生成的种子，e为存种子b的点
//bool st[N];
//int dist[N];
//queue<int>q;
//int n, m;
////这里与一搬得连接表不同，c是杂交后得目标种子
//void add(int a, int b, int c)
//{
//    e[idx] = b, target[idx] = c, ne[idx] = h[a], h[a] = idx++;
//}
//void spfa()
//{
//    while (q.size())
//    {
//        int x = q.front();
//        q.pop();
//        st[x] = false;
//        for (int i = h[x]; i != -1; i = ne[i])
//        {
//            int y = e[i], z = target[i];
//            if (dist[z] > max(dist[x], dist[y]) + max(w[x], w[y]))//比如杂交出c的方法很多，取时间最小的，所以需要判断
//            {
//                dist[z] = max(dist[x], dist[y]) + max(w[x], w[y]);//这两个max需要分开写
//                if (!st[z])
//                {
//                    q.push(z);//生成的目标种子插入队列
//                    st[z] = true;
//                }
//            }
//        }
//    }
//}
//int main()
//{
//    int k, T;
//    cin >> n >> m >> k >> T;
//    memset(h, -1, sizeof h);
//    for (int i = 1; i <= n; i++)
//    {
//        int t;
//        cin >> t;
//        w[i] = t;//表示每个种子成熟时间
//    }
//    memset(dist, 0x3f, sizeof dist);
//    while (m--)
//    {
//        int j;
//        cin >> j;//表示已有的种子
//        dist[j] = 0;
//        q.push(j);
//    }
//    while (k--)
//    {
//        int a, b, c;
//        cin >> a >> b >> c;
//        //因为是无向的
//        add(a, b, c);
//        add(b, a, c);
//    }
//    spfa();
//    cout << dist[T] << endl;
//    return 0;
//}


//题目：01背包问题
//有 N件物品和一个容量是 V的背包。每件物品只能使用一次。
//第 i件物品的体积是 vi，价值是 wi。
//求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
//输出最大价值。
//输入格式
//第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
//接下来有 N行，每行两个整数 vi, wi，用空格隔开，分别表示第 i件物品的体积和价值。
//输出格式
//输出一个整数，表示最大价值。
//数据范围
//0 < N, V≤1000，0 < vi, wi≤1000
//输入样例
//4 5
//1 2
//2 4
//3 4
//4 5
//输出样例：
//8

//一维
//#include <iostream>
//#include <algorithm>
//
//using namespace std;
//
//const int N = 1010;
//
//int n, m;
//int v[N], w[N];
//int f[N];
//
//int main()
//{
//    cin >> n >> m;
//
//    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
//
//    //如果使用顺序，会先更新f[4],再更新f[7]，对于这个书包问题来讲，就是有可能，在更新f[4]的时候，
//    //已经把这次能加的物品加进来了，然后更新f[7]的时候，还有可能再加一次，所以必须使用逆序，
//    //保证，f[4]是没有加入新物品前，背包里的最优解。
//    for (int i = 1; i <= n; i++)
//        for (int j = m; j >= v[i]; j--)
//            f[j] = max(f[j], f[j - v[i]] + w[i]);
//
//    cout << f[m] << endl;
//
//    return 0;
//}

//二维
//#include<iostream>
//#include<algorithm>
//using namespace std;
//const int N = 1010;
//int n, m;
//int v[N], w[N];//v代表每个物品得体积，w代表每个物品得价值
//int f[N][N];
//
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
//    //(2)当前背包容量不够（j < v[i]），没得选，因此前 i个物品最优解即为前 i−1个物品最优解：
//    //对应代码：f[i][j] = f[i - 1][j]。
//    //(3)当前背包容量够，可以选，因此需要决策选与不选第 i个物品：
//    //选：f[i][j] = f[i - 1][j - v[i]] + w[i]。
//    //不选：f[i][j] = f[i - 1][j] 。
//    //我们的决策是如何取到最大价值，因此以上两种情况取 max() 。
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//        {
//            f[i][j] = f[i - 1][j];
//            if (j >= v[i])
//            {
//                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
//            }
//        }
//    cout << f[n][m] << endl;
//    return 0;
//}

//题目：完全背包问题
//有 N种物品和一个容量是 V的背包，每种物品都有无限件可用。
//第 i种物品的体积是 vi，价值是 wi。
//求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
//输出最大价值。
//输入格式
//第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
//接下来有 N行，每行两个整数 vi, wi，用空格隔开，分别表示第 i种物品的体积和价值。
//输出格式
//输出一个整数，表示最大价值。
//数据范围
//0 < N, V≤1000，0 < vi, wi≤1000
//输入样例
//4 5
//1 2
//2 4
//3 4
//4 5
//输出样例：
//10

//二维三重循环完全背包问题
//#include<iostream>
//#include<algorithm>
//using namespace std;
//const int N = 1010;
//int v[N], w[N];
//int dp[N][N];
//int n, m;
//
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
//    for (int i = 1; i <= n; i++)
//        for (int j = 0; j <= m; j++)
//            for (int k = 0; k * v[i] <= j; k++)//这里k是因为选多个相同得背包不能超过容量j
//                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i] * k] + w[i] * k);
//    cout << dp[n][m] << endl;
//    return 0;
//}

//二维二重完全背包优化

//#include<iostream>
//#include<algorithm>
//using namespace std;
//const int N = 1010;
//int v[N], w[N];
//int dp[N][N];
//int n, m;
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
//    for (int i = 1; i <= n; i++)
//        for (int j = 0; j <= m; j++)
//        {
//            dp[i][j] = dp[i - 1][j];//算i-1之前得状态
//            if (j >= v[i])//j要大于容量才能进入
//            {
//                //这里是因为完全背包问题，与01背包有相似，但是下标有不同，上面那个式子已经求了前面得状态。
//                //这里赋上三重循环到二维循环得公式推导
//                //dp[i][j - v] = max(dp[i - 1][j - v], dp[i - 1][j - 2 * v] + w, dp[i - 1][j - 3 * v] + 2 * w, .....)；
//                //dp[i][j]= max(dp[i - 1][j], dp[i - 1][j - v] + w, dp[i - 1][j - 2 * v] + 2 * w, dp[i - 1][j - 3 * v] + 3 * w);
//                //因为01背包只能用一次所以要从未更新前得状态更新，要用i-1而不是i
//                dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
//            }
//        }
//    cout << dp[n][m] << endl;
//    return 0;
//}

//一维（与01背包相似得从二重循环转化为一重循环）
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int v[N], w[N];
int dp[N];
int n, m;
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    for (int i = 1; i <= n; i++)
        for (int j = v[i]; j <= m; j++)
        {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    cout << dp[m] << endl;
    return 0;
}